﻿#include <iostream>
using namespace std;
#include "MyListNode.h" //引入列表节点类;
template <typename T> class MyList { //列表模板类

private:
    int _size; ListNodePosi(T) header; ListNodePosi(T) trailer; //规模、头哨兵、尾哨兵

protected:
    void init(); //列表创建时的初始化
    int clear(); //清除所有节点
    void copyNodes(ListNodePosi(T), int); //复制列表中自位置p起的n项
    void merge(ListNodePosi(T)&, int, MyList<T>&, ListNodePosi(T), int); //归并
    void mergeSort(ListNodePosi(T)&, int); //对从p开始连续的n个节点归并排序
    void selectionSort(ListNodePosi(T) p, int n); //对从p开始连续的n个节点选择排序
    void insertionSort(ListNodePosi(T) p, int n); //对从p开始连续的n个节点插入排序
    void radixSort(ListNodePosi(T), int); //对从p开始连续的n个节点基数排序

public:
    // 构造函数
    MyList() { init(); } //默认
    MyList(MyList<T> const& L); //整体复制列表L
    MyList(MyList<T> const& L, Rank r, int n); //复制列表L中自第r项起的n项
    MyList(ListNodePosi(T) p, int n); //复制列表中自位置p起的n项
 // 析构函数
    ~MyList(); //释放（包含头、尾哨兵在内的）所有节点
 // 只读访问接口
    Rank size() const { return _size; } //规模
    bool empty() const { return _size <= 0; } //判空
    T& operator[] (Rank r) const; //重载，支持循秩访问（效率低）
    ListNodePosi(T) first() const { return header->succ; } //首节点位置
    ListNodePosi(T) last() const { return trailer->pred; } //末节点位置
    bool valid(ListNodePosi(T) p) //判断位置p是否对外合法
    {
        return p && (trailer != p) && (header != p);
    } //将头、尾节点等同于NULL
    ListNodePosi(T) find(T const& e) const //无序列表查找
    {
        return find(e, _size, trailer);
    }
    ListNodePosi(T) find(T const& e, int n, ListNodePosi(T) p) const; //无序区间查找
    ListNodePosi(T) search(T const& e) const //有序列表查找
    {
        return search(e, _size, trailer);
    }
    ListNodePosi(T) search(T const& e, int n, ListNodePosi(T) p) const; //有序区间查找
    ListNodePosi(T) selectMax(ListNodePosi(T) p, int n); //在p及其n-1个后继中选出最大者
    ListNodePosi(T) selectMax() { return selectMax(header->succ, _size); } //整体最大者
// 可写访问接口
    ListNodePosi(T) insertAsFirst(T const& e); //将e当作首节点插入
    ListNodePosi(T) insertAsLast(T const& e); //将e当作末节点插入
    ListNodePosi(T) insertA(ListNodePosi(T) p, T const& e); //将e当作p的后继插入（After）
    ListNodePosi(T) insertB(ListNodePosi(T) p, T const& e); //将e当作p的前驱插入（Before）
    T remove(ListNodePosi(T) p); //删除合法位置p处的节点,返回被删除节点
    void merge(MyList<T>& L) { merge(first(), size, L, L.first(), L._size); } //全列表归并
    void sort(ListNodePosi(T) p, int n); //列表区间排序
    void sort() { sort(first(), _size); } //列表整体排序
    int deduplicate(); //无序去重
    int uniquify(); //有序去重
    void reverse(); //前后倒置（习题）
 // 遍历
    void traverse(void (*) (T&)); //遍历，依次实施visit操作（函数指针，只读或局部性修改）
    template < typename VST> //操作器
    void traverse(VST&); //遍历，依次实施visit操作（函数对象，可全局性修改）

}; //List


//===========================MyList实现==================================
template <typename T> 
void MyList<T>::init() { //列表初始化，在创建列表对象时统一调用
    header = new MyListNode<T>; //创建头哨兵节点
    trailer = new MyListNode<T>; //创建尾哨兵节点
    header->succ = trailer; header->pred = NULL;
    trailer->pred = header; trailer->succ = NULL;
    _size = 0; //记录规模
}
template<typename T>
int MyList<T>::clear()//清空列表
{
    int oldSize = _size;
    while (_size>0)//反复删除首节点，直到列表变空
    {
        remove(header->succ);
    }
    return oldSize;
}

template<typename T>
void MyList<T>::insertionSort(ListNodePosi(T) p, int n)
{
    for (int r = 0; r < n; r++) { //逐一为各节点
        insertA(search(p->data, r, p), p->data); //查找适当的位置并插入
        p = p->succ; remove(p->pred); //转向下一节点
    }
}

template<typename T>
void MyList<T>::selectionSort(ListNodePosi(T) p, int n)//从起始于位置p的n个元素中选出最大者
{
    ListNodePosi(T) head = p->pred; ListNodePosi(T) tail = p;
    for (int i = 0; i < n; i++) tail = tail->succ; //待排序区间为(head, tail)
    while (1 < n) { //在至少还剩两个节点之前，在待排序区间内
        ListNodePosi(T) max = selectMax(head->succ, n); //找出最大者（歧义时后者优先）
        insertB(tail, remove(max)); //将其移至无序区间末尾（作为有序区间新的首元素）
        tail = tail->pred; n--;
    }
}

//O(n)线性正比于列表规模
template<typename T>
MyList<T>::~MyList()
{
    clear();
    delete header;
    delete trailer;
}

template<typename T>
T& MyList<T>::operator[](Rank r) const
{
    ListNodePosi(T) p = first(); //从首节点出发
        while (0 < r--) p = p->succ; //顺数第r个节点即是
        return p->data; //目标节点，返回其中所存元素
}

template<typename T>
ListNodePosi(T) MyList<T>::find(T const& e, int n, ListNodePosi(T) p) const//在无序列表内节点p（可能是trailer）的n个（真）前驱中，找到等于e的最后者
{
    while (0 < n--) //（0 <= n <= rank(p) < _size）对于p的最近的n个前驱，从右向左
        if (e == (p = p->pred)->data) return p; //逐个比对，直至命中或范围越界
    return NULL; //p越出左边界意味着区间内不含e，查找失败
    //失败时，返回NULL
}

template<typename T>//在有序列表内节点p（可能是trailer）的n个（真）前驱中，找到不大于e的最后者
ListNodePosi(T) MyList<T>::search(T const& e, int n, ListNodePosi(T) p) const
{
    // assert: 0 <= n <= rank(p) < _size
     do {
          p = p->pred;
          n--;  //从右向左
     } while ((-1 < n) && (e < p->data)); //逐个比较，直至命中或越界
     return p; //返回查找终止的位置    
//失败时，返回区间左边界的前驱（可能是header）——调用者可通过valid()判断成功与否
}

template<typename T>
ListNodePosi(T) MyList<T>::selectMax(ListNodePosi(T) p, int n)
{
    ListNodePosi(T) max = p; //最大者暂定为首节点p
    for (ListNodePosi(T) cur = p; 1 < n; n--) //从首节点p出发，将后续节点逐一与max比较
           if (!lt((cur = cur->succ)->data, max->data)) //若当前元素不小于max，则
              max = cur; //更新最大元素位置记录
    return max; //返回最大节点位置
}

template<typename T>
ListNodePosi(T) MyList<T>::insertB(ListNodePosi(T) p, T const& e)
{
    _size++; 
    return p->insertAsPred(e);
}

template<typename T>
T MyList<T>::remove(ListNodePosi(T) p)
{
    T e = p->data;//备份待删除节点的值（设类型T可直接赋值）
    p->pred->succ = p->succ;
    p->succ->pred = p->pred;
    delete p;
    _size--;
    return e;
}

template<typename T>
int MyList<T>::deduplicate()
{
    if (_size < 2)return 0;
    int oldSize = _size; 
    ListNodePosi(T) p = first();
    for (Rank r = 0; p != trailer; p = p->succ) {//O(n)
        if (ListNodePosi(T) q = find(p->data, r, p))
            remove(q); //此时q与p雷同，但删除前者更为简明
        else r++; //r为无重前缀的长度
    }   
    return oldSize - _size; //删除元素总数 
}

template<typename T>
int MyList<T>::uniquify()
{
    if (_size<2)return 0;
    int oldSize = _size;
    ListNodePosi(T) p = first();
    ListNodePosi(T) q;
    while (trailer!=(q=p->succ))
    {
        if (p->data != q->data)p = q;
        else remove(q);
    }
    return oldSize-_size;
}//O(n)
